#include <iostream>

using namespace std;

void printArray(char (*array)[2], int len)
{
    for (int i = 0; i < len; i++)
    {
        cout << array[i][0] << array[i][1];
        if (i != len - 1)
            cout << " ";
        else
            cout << endl;
    }
}

void swap(char *arr1, char *arr2)
{
    char tmp[2];
    tmp[0] = arr1[0];
    tmp[1] = arr1[1];
    arr1[0] = arr2[0];
    arr1[1] = arr2[1];
    arr2[0] = tmp[0];
    arr2[1] = tmp[1];
}

void bubbleSort(char (*array)[2], int len)
{
    bool is_stable = true;
    char tmp[2];
    for (int i = 0; i < len; i++)
    {
        for (int j = len - 1; j > i; j--)
        {
            if (array[j][1] < array[j - 1][1])
            {
                if (is_stable && array[j][0] == array[j - 1][0] && array[j][1] > array[j - 1][1])
                {
                    is_stable = false;
                }
                swap(array[j], array[j - 1]);
            }
        }
    }
    printArray(array, len);
    if (is_stable)
    {
        cout << "Stable" << endl;
    }
    else
    {
        cout << "Not stable" << endl;
    }
}

void selectionSort(char (*array)[2], int len)
{
    bool is_stable = true;
    int mini;
    char tmp[2];
    for (int i = 0; i < len; i++)
    {
        mini = i;
        for (int j = i + 1; j < len; j++)
        {
            if (array[j][1] < array[mini][1])
            {
                mini = j;
            }
        }
        if (i != mini)
        {
            if (is_stable && array[i][0] == array[mini][0] && array[i][1] > array[mini][1])
            {
                is_stable = false;
            }
            swap(array[i], array[mini]);
        }
    }
    printArray(array, len);
    if (is_stable)
    {
        cout << "Stable" << endl;
    }
    else
    {
        cout << "Not stable" << endl;
    }
}

int main()
{
    int n;
    cin >> n;
    char array[n][2], array1[n][2];
    for (int i = 0; i < n; i++)
    {
        cin >> array[i];
        array1[i][0] = array[i][0];
        array1[i][1] = array[i][1];
    }

    bubbleSort(array, n);
    selectionSort(array1, n);
}
